package FloodFill;

import java.util.*;

/**
 * @author: yangwk
 * @date: 2023/8/11
 * @description:
 **/
public class WaterFlood {
    public static void main(String[] args) {
        int[][] arr = {
                {0, 1, 1, 0},
                {1, 1, 1, 1},
                {0, 0, 1, 1}};
        int[] water = water(arr);
        System.out.println(water);
    }

    static boolean[][] visited = new boolean[1000][1000];

    public static int[] water(int[][] arr) {
        int rowLength = arr.length;
        int colLength = arr[0].length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < rowLength; i++) {
            for (int j = 0; j < colLength; j++) {
                if (arr[i][j] == 0 && !visited[i][j]) {
                    list.add(dfs(arr, i, j, 0));
                }
            }
        }
        int[] water = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            water[i] = list.get(i);
        }
        Arrays.sort(water);
        return water;
    }

    public int bfs(int[][] land, int x, int y) {
        int m = land.length, n = land[0].length;
        int res = 0;
        Queue<int[]> queue = new ArrayDeque<int[]>();
        queue.offer(new int[]{x, y});
        land[x][y] = -1;
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int currX = arr[0], currY = arr[1];
            res++;
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (dx == 0 && dy == 0) {
                        continue;
                    }
                    if (currX + dx < 0 || currX + dx >= m || currY + dy < 0 || currY + dy >= n || land[currX + dx][currY + dy] != 0) {
                        continue;
                    }
                    land[currX + dx][currY + dy] = -1;
                    queue.offer(new int[]{currX + dx, currY + dy});
                }
            }
        }
        return res;
    }

    public static int dfs(int[][] arr, int x, int y, int color) {

        if (!inArea(arr, x, y)) {
            return 0;
        }
        if (visited[x][y]) {
            return 0;
        }
        if (arr[x][y] != color) {
            return 0;
        }
        arr[x][y] = 1;
        visited[x][y] = true;
        int res = dfs(arr, x + 1, y, color) +
                dfs(arr, x - 1, y, color) +
                dfs(arr, x, y + 1, color) +
                dfs(arr, x, y - 1, color) +
                dfs(arr, x + 1, y + 1, color) +
                dfs(arr, x - 1, y - 1, color) +
                dfs(arr, x + 1, y - 1, color) +
                dfs(arr, x - 1, y + 1, color) + 1;
        return res;
    }

    public static boolean inArea(int[][] arr, int x, int y) {
        int rowLength = arr.length;
        int colLength = arr[0].length;
        if (x >= 0 && x < rowLength && y >= 0 && y < colLength) {
            return true;
        }
        return false;
    }
}
